package leetcode_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;



public class FindSubstringHelp {
	static class Helper{
		int index;
		int value;
		public Helper(int index, int value) {
			this.index = index;
			this.value = value;
		}
	}
	
	
	public static void main(String[] args) {
		String s="barfoothefoobarman";
		String strs[]= {"foo","bar"};
		String s2="wordgoodgoodgoodbestword";
		String strs2[]= {"word","good","best","good"};
		findSubstring(s2, strs2);
		
		
	}
	
	public static List<Helper> findSubstringHelp(String s, String[] words){
		List<Helper> res= new ArrayList<Helper>();
		int length=words[0].length();
		int i=0;
		while(i<=s.length()-length){
			for(int j=0;j<words.length;++j) {
				if(words[j].equals(s.substring(i, i+length))) {//找到
					Helper helper=new Helper(j, i);
					res.add(helper);
				}
			}
			++i;
		}
		return res;
	}
	
	public static List<Integer> findSubstring(String s, String[] words){
		List<Helper> helpers=findSubstringHelp(s, words);
		List<Integer> res=new ArrayList<Integer>();
		int now=0,count=0;
		boolean [] flags=new boolean[words.length];
		boolean flag=true;
		while(now<=helpers.size()-words.length) {
			Arrays.fill(flags, false);
			flag=true;
			int index=now+1;
			flags[helpers.get(now).index]=true;
			count=1;
			while(count<words.length) {
				if(flags[helpers.get(index).index]==true) {//已经发现有此子串
					flag=false;
					break;
				}
				else {
					flags[helpers.get(index).index]=true;
					++count;
					++index;
				}
			}
			if(flag) 
				res.add(helpers.get(now).value);
			++now;
		}
		return res;
		
	}

}
